package day07;

/**
 * 给定字符串 S and T，找出 S 中最短的（连续）子串 W ，使得 T 是 W 的 子序列 。
 *
 * 如果 S 中没有窗口可以包含 T 中的所有字符，返回空字符串 ""。如果有不止一个最短长度的窗口，返回开始位置最靠左的那个。
 *
 * 示例 1：
 *
 * 输入：
 * S = "abcdebdde", T = "bde"
 * 输出："bcde"
 * 解释：
 * "bcde" 是答案，因为它在相同长度的字符串 "bdde" 出现之前。
 * "deb" 不是一个更短的答案，因为在窗口中必须按顺序出现 T 中的元素。
 *
 *
 */
public class Solution8 {
    public String minWindow(String s1, String s2) {
        char [] s=s1.toCharArray();
        char [] t=s2.toCharArray();//转化的数组
        int left=0;
        int right=0;
        int i=0;//循环t
        int start=0;//起始位置
        int minlength=s.length+1;//最短长度  //abcdebdde  a->e   a-d
        //abcdef  bcd
        while(left<s.length){ //遍历字符的起始位置
            if(s[left]==t[i]){
                i++;
            }
            if(i==t.length){//包含了
                right=left;//备份
                while(i>0){
                    if(s[left]==t[i-1]){ //相等，回退
                        i--;//退回，恢复0
                    }
                    left--;
                }
                left++;
                //bcdef
                //bcde
                // bcd
                if(right-left+1<minlength){ //保存最短
                    minlength=right-left+1;//缩短长度
                    start=left;
                }
            }
            left++;
        }
        if(minlength==s.length+1){//整体相等，不变，无解
            return "";

        }else{
            return s1.substring(start,start+minlength);
        }
    }
}
